package ercahshu

import "math"

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	ans := make([]int, 0)
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)
		ans = append(ans, node.Val)
		dfs(node.Right)
	}
	dfs(root)
	return shengxu(ans)
}

func shengxu(nums []int) bool {
	left, right := 0, 1
	for right < len(nums) {
		if nums[left] > nums[right] {
			return false
		}
		left++
		right++
	}
	return true
}

func isValidBST1(root *TreeNode) bool {
	// 使用三个变量
	var dfs func(node *TreeNode, r1, r2 int) bool
	dfs = func(node *TreeNode, r1, r2 int) bool {
		if node == nil {
			return true
		}
		return r1 < node.Val && r2 > node.Val && dfs(root.Left, r1, node.Val) && dfs(root.Right, node.Val, r2)
	}
	return dfs(root, math.MinInt, math.MaxInt)
}

func isValidBST2(root *TreeNode) bool {
	if root == nil {
		return true
	}
	var pre *TreeNode
	var dfs func(node *TreeNode) bool
	dfs = func(node *TreeNode) bool {
		if node == nil {
			return true
		}
		left := dfs(node.Left)
		if pre != nil && node.Val <= pre.Val {
			return false
		}
		pre = node
		right := dfs(node.Right)
		return left && right
	}
	return dfs(root)
}
